/*
 * @lc app=leetcode.cn id=799 lang=cpp
 *
 * [799] 香槟塔
 */

// @lc code=start
class Solution {
public:
    double champagneTower(int poured, int query_row, int query_glass) {
        vector<double> rows = {(double)poured};
        for (int i = 1; i <= query_row; i++) {
            vector<double> nextrows(i + 1, (double)0);
            for (int j = 0; j < i; j++) {
                double val = rows[j];
                if (val > 1) {
                    nextrows[j] += (val - 1) / 2;
                    nextrows[j + 1] += (val - 1) / 2;
                }
            }
            rows = nextrows;
        }
        return min(1.0, rows[query_glass]);
    }
};
// @lc code=end
